package J0120;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Solution2 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        //如果左边为空 或者左边不在栈里就直接跳出打印 然后进右边
        //否则继续向左
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tmp = root;
        while(tmp != null || !stack.isEmpty()) {
            while(tmp != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }
            //走到这一步说明 tmp的左边都等于空了
            TreeNode tree = stack.pop();
            list.add(tree.val);
            tmp = tree.right;
        }
        return list;
    }
}
